{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Paths in Maze That Lead to Same Room"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: numberOfPaths"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #殊途同归"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>迷宫由 <code>n</code> 个从 <code>1</code> 到 <code>n</code> 的房间组成，有些房间由走廊连接。给定一个二维整数数组 <code>corridors</code>，其中 <code>corridors[i] = [room1<sub>i</sub>, room2<sub>i</sub>]</code>&nbsp;表示有一条走廊连接 <code>room1<sub>i</sub></code> 和<code>room2<sub>i</sub></code>，允许迷宫中的一个人从 <code>room1<sub>i</sub></code> 到 <code>room1<sub>i</sub></code> ，<strong>反之亦然</strong>。</p>\n",
    "\n",
    "<p>迷宫的设计者想知道迷宫有多让人困惑。迷宫的&nbsp;<strong>混乱分数&nbsp;</strong>是&nbsp;<strong>长度为 3</strong> 的不同的环的数量。</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>例如, <code>1 → 2 → 3 → 1</code>&nbsp;是长度为 3 的环, 但&nbsp;<code>1 → 2 → 3 → 4</code> 和&nbsp;<code>1 → 2 → 3 → 2 → 1</code> 不是。</li>\n",
    "</ul>\n",
    "\n",
    "<p>如果在第一个环中访问的一个或多个房间&nbsp;<strong>不在&nbsp;</strong>第二个环中，则认为两个环是&nbsp;<strong>不同&nbsp;</strong>的。</p>\n",
    "\n",
    "<p data-group=\"1-1\">返回<em>迷宫的混乱分数</em>。</p>\n",
    "\n",
    "<p><strong class=\"example\">示例 1:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/11/14/image-20211114164827-1.png\" style=\"width: 440px; height: 350px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 5, corridors = [[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]\n",
    "<strong>输出:</strong> 2\n",
    "<strong>解释:</strong>\n",
    "一个长度为 3 的环为 4→1→3→4，用红色表示。\n",
    "注意，这是与 3→4→1→3 或 1→3→4→1 相同的环，因为房间是相同的。\n",
    "另一个长度为 3 的环为 1→2→4→1，用蓝色表示。\n",
    "因此，有两个长度为 3 的不同的环。\n",
    "</pre>\n",
    "\n",
    "<p><strong class=\"example\">示例&nbsp;2:</strong></p>\n",
    "<img src=\"https://assets.leetcode.com/uploads/2021/11/14/image-20211114164851-2.png\" style=\"width: 329px; height: 250px;\" />\n",
    "<pre>\n",
    "<strong>输入:</strong> n = 4, corridors = [[1,2],[3,4]]\n",
    "<strong>输出:</strong> 0\n",
    "<strong>解释:</strong>\n",
    "没有长度为 3 的环。</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= corridors.length &lt;= 5 * 10<sup>4</sup></code></li>\n",
    "\t<li><code>corridors[i].length == 2</code></li>\n",
    "\t<li><code>1 &lt;= room1<sub>i</sub>, room2<sub>i</sub> &lt;= n</code></li>\n",
    "\t<li><code>room1<sub>i</sub> != room2<sub>i</sub></code></li>\n",
    "\t<li>\n",
    "\t<p data-group=\"1-1\">没有重复的走廊。</p>\n",
    "\t</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [paths-in-maze-that-lead-to-same-room](https://leetcode.cn/problems/paths-in-maze-that-lead-to-same-room/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [paths-in-maze-that-lead-to-same-room](https://leetcode.cn/problems/paths-in-maze-that-lead-to-same-room/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['5\\n[[1,2],[5,2],[4,1],[2,4],[3,1],[3,4]]', '4\\n[[1,2],[3,4]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, G: List[List[int]], mod: int) -> int:\n",
    "        m, n = len(G), len(G[0])\n",
    "        dp = [{} for _ in range(n + 1)]; dp[1][0] = 1\n",
    "        for i, j in product(range(m), range(n)): dp[j + 1] = {(k + G[i][j]) % mod: (dp[j + 1].get(k, 0) + dp[j].get(k, 0)) % 1000000007 for k in dp[j + 1] | dp[j]}\n",
    "        return dp[-1].get(0, 0)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "import copy\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        my_mat=[[0]*k for i in range(len(grid[0])+1)]\n",
    "        sum1=0\n",
    "        for i in range(len(grid[0])):\n",
    "            sum1=(sum1+grid[0][i])%k\n",
    "            my_mat[i+1][sum1]+=1\n",
    "        \n",
    "        for i in range(1,len(grid)):\n",
    "            temp_mat=[[0]*k for i in range(len(grid[0])+1)]\n",
    "            for j in range(len(grid[0])):\n",
    "                list_up=my_mat[j+1]\n",
    "                list_left=temp_mat[j]\n",
    "                for v in range(k):\n",
    "                    next_index=(v+grid[i][j])%k\n",
    "                    temp_sum=list_up[v]+list_left[v]\n",
    "                    temp_mat[j+1][next_index]=temp_sum%(10**9+7)\n",
    "            my_mat=copy.deepcopy(temp_mat)\n",
    "\n",
    "        return my_mat[-1][0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        n = len(grid[0])\n",
    "\n",
    "        dp = [[0] * k for _ in range(n)]\n",
    "        dp[0][0] = 1\n",
    "\n",
    "        for row in grid:\n",
    "            temp = [0] * k\n",
    "            for j in range(k):\n",
    "                temp[(j + row[0]) % k] = dp[0][j]\n",
    "            dp[0] = temp\n",
    "\n",
    "            for i in range(1, n):\n",
    "                temp = [0] * k\n",
    "                for j in range(k):\n",
    "                    temp[(j + row[i]) % k] = dp[i][j] + dp[i-1][j]\n",
    "                dp[i] = temp\n",
    "        \n",
    "        return dp[-1][0] % (10 ** 9 + 7)\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        down ,right = len(grid),len(grid[0])\n",
    "        dp = [[0] * k for _ in range(right + 1)]\n",
    "        dp[0][0] = 1\n",
    "        for i,j in product(range(down),range(right)):\n",
    "            t = [(x + y) % 1000000007 for x,y in zip(dp[j],dp[j-1])]\n",
    "            d = grid[i][j] % k\n",
    "            dp[j] = t[d:] + t[:d]\n",
    "        return dp[right-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, G: List[List[int]], mod: int) -> int:\n",
    "        m, n = len(G), len(G[0])\n",
    "        dp = [[0]*mod for _ in range(n + 1)]; \n",
    "        dp[0][0] = 1\n",
    "        for i, j in product(range(m), range(n)): \n",
    "            t = [(x+y) % 1000000007 for x,y in zip(dp[j],dp[j-1])]\n",
    "            d = G[i][j] % mod\n",
    "            dp[j] = t[d:] + t[:d]\n",
    "        return dp[n-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, G: List[List[int]], k: int) -> int:\n",
    "        m, n = len(G), len(G[0])\n",
    "        dp = [[0]*k for _ in range(n + 1)]; \n",
    "        dp[0][0] = 1\n",
    "        for i, j in product(range(m), range(n)): \n",
    "            t = [(x+y) % 1000000007 for x,y in zip(dp[j],dp[j-1])]\n",
    "            d = G[i][j] % k\n",
    "            dp[j] = t[d:] + t[:d]\n",
    "        return dp[n-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[0] * k for _ in range(n + 1)]\n",
    "        f[1][0] = 1\n",
    "        for i, row in enumerate(grid):\n",
    "            fj = [[0] * k for _ in range(n + 1)]\n",
    "            fj[1][0] = 1\n",
    "            for j, x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    fj[j + 1][(v + x) % k] = (fj[j][v] + f[j + 1][v]) % MOD\n",
    "            f = fj\n",
    "        return f[n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        f = [[[0] * k for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "        f[1][1][grid[0][0] % k] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                for kk in range(k):\n",
    "                    cur = (grid[i - 1][j - 1] + kk) % k\n",
    "                    f[i][j][cur] += f[i - 1][j][kk] + f[i][j - 1][kk]\n",
    "                    f[i][j][cur] %= mod\n",
    "        return f[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        f[0][1][0] = 1\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    f[i + 1][j + 1][(v + x) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD\n",
    "        return f[m][n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[[0]*k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        # 因为从 dp[1][1]开始那么只能有  dp[0][1]和 dp[1][0]那获取，所以只能是这两个\n",
    "        dp[1][0][0]=1\n",
    "        mod = 10**9 + 7\n",
    "        for i,row in enumerate(grid):\n",
    "            for j,x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    #  (a+b)%mod = (x+b)%mod\n",
    "                    dp[i+1][j+1][(x+v)%k]=(dp[i][j+1][v]+dp[i+1][j][v])%mod\n",
    "        return dp[m][n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        f[0][1][0] = 1\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    f[i + 1][j + 1][(v + x) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD\n",
    "        return f[m][n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        dp=[[[0]*k for _ in range(m+1)] for _ in range(n+1)]\n",
    "        dp[0][1][0]=1\n",
    "        mod=10**9+7\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                for v in range(k):\n",
    "                    dp[i+1][j+1][(v+grid[i][j])%k]=(dp[i][j+1][v]+dp[i+1][j][v])%mod\n",
    "        return dp[-1][-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        f[0][1][0] = 1\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    f[i + 1][j + 1][(v + x) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD\n",
    "        return f[m][n][0] "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        f[0][1][0] = 1\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    f[i + 1][j + 1][(v + x) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD\n",
    "        return f[m][n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        f[0][1][0] = 1\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    f[i + 1][j + 1][(v + x) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD\n",
    "        return f[m][n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "# DP（刷表法更新）\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid),  len(grid[0])\n",
    "        dp = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        dp[0][1][0] = 1\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                for kk in range(k):\n",
    "                    dp[i + 1][j + 1][(kk + x) %\n",
    "                                     k] += dp[i][j + 1][kk] + dp[i + 1][j][kk]\n",
    "                    dp[i + 1][j + 1][(kk + x) % k] %= MOD\n",
    "        return dp[-1][-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        f[0][1][0] = 1\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    f[i + 1][j + 1][(v + x) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD\n",
    "        return f[m][n][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0] * k for _ in range(n)] for _ in range(m)]\n",
    "        dp[m - 1][n - 1][grid[m - 1][n - 1] % k] = 1\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for r in range(k):\n",
    "                dp[i][n - 1][r] = dp[i + 1][n - 1][(r - grid[i][n - 1] % k) % k]\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            for r in range(k):\n",
    "                dp[m - 1][j][r] = dp[m - 1][j + 1][(r - grid[m - 1][j] % k) % k]\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n - 2, - 1, -1):\n",
    "                for r in range(k):\n",
    "                    need = (r - grid[i][j] % k) % k\n",
    "                    dp[i][j][r] = (dp[i + 1][j][need] + dp[i][j + 1][need]) % MOD\n",
    "        return dp[0][0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, m = len(grid), len(grid[0])\n",
    "\n",
    "        f = [[[0] * 50 for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "\n",
    "        f[0][1][0] = 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                for p in range(k):\n",
    "                    f[i + 1][j + 1][(p + grid[i][j]) % k] += (f[i][j + 1][p] + f[i + 1][j][p]) % MOD\n",
    "\n",
    "        return f[-1][-1][0] % MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10**9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0] * k for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        dp[0][0][grid[0][0] % k] = 1\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for s in range(k):\n",
    "                    # 如果从上面来\n",
    "                    if i - 1 >= 0:\n",
    "                        dp[i][j][(s + grid[i][j]) % k] += dp[i-1][j][s]\n",
    "                        dp[i][j][(s + grid[i][j]) % k] %= MOD\n",
    "                    # 如果从左边来\n",
    "                    if j - 1 >= 0:\n",
    "                        dp[i][j][(s + grid[i][j]) % k] += dp[i][j-1][s]\n",
    "                        dp[i][j][(s + grid[i][j]) % k] %= MOD\n",
    "                        \n",
    "        return dp[m-1][n-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        f[0][1][0] = 1\n",
    "        for i in range(len(grid)):\n",
    "            for j, x in enumerate(grid[i]):\n",
    "                for v in range(k):\n",
    "                    f[i + 1][j + 1][(v + x) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD\n",
    "        return f[m][n][0]\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        modp = 10 ** 9 + 7\n",
    "        f = [[[0] * k for _ in range(m)] for _ in range(n)]\n",
    "        f[0][0][grid[0][0] % k] = 1\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                for p in range(k):\n",
    "                    t = f[i][j][p] % modp\n",
    "                    if t == 0: continue\n",
    "                    if i + 1 < n:\n",
    "                        f[i + 1][j][(p + grid[i + 1][j]) % k] += t\n",
    "                    if j + 1 < m:\n",
    "                        f[i][j + 1][(p + grid[i][j + 1]) % k] += t\n",
    "\n",
    "        return f[n - 1][m - 1][0] % modp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MOD = 10 ** 9 + 7\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        # dp[i][j][t]: at position(i, j), diviosr = t\n",
    "        dp = [[[0] * k for _ in range(col)] for _ in range(row)]\n",
    "        dp[0][0][grid[0][0] % k] = 1\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                for t in range(k):\n",
    "                    if i > 0:\n",
    "                        # 向下\n",
    "                        index = (t + grid[i][j]) % k\n",
    "                        dp[i][j][index] += dp[i-1][j][t]\n",
    "                        dp[i][j][index] %= self.MOD\n",
    "                    if j > 0:\n",
    "                        # 向右\n",
    "                        index = (t + grid[i][j]) % k\n",
    "                        dp[i][j][index] += dp[i][j-1][t]\n",
    "                        dp[i][j][index] %= self.MOD\n",
    "        \n",
    "        return dp[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], K: int) -> int:\n",
    "        #将余数k看作补充状态,套路\n",
    "        mod = 10**9+7\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        f = [[[0]*K for _ in range(n)] for _ in range(m)]\n",
    "        f[0][0][grid[0][0]%K] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for k in range(K):\n",
    "                    t=grid[i][j]\n",
    "                    #从上方到达\n",
    "                    if i>0:\n",
    "                        f[i][j][k] = (f[i][j][k]+f[i-1][j][(k-t+K)%K])%mod\n",
    "                    if j>0:\n",
    "                        f[i][j][k] = (f[i][j][k]+f[i][j-1][(k-t+K)%K])%mod\n",
    "        return f[m-1][n-1][0]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    MOD = 10 ** 9 + 7\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        row, col = len(grid), len(grid[0])\n",
    "        # dp[i][j][t]: at position(i, j), diviosr = t\n",
    "        dp = [[[0] * k for _ in range(col)] for _ in range(row)]\n",
    "        dp[0][0][grid[0][0] % k] = 1\n",
    "\n",
    "        for i in range(row):\n",
    "            for j in range(col):\n",
    "                for t in range(k):\n",
    "                    if i > 0 and dp[i-1][j][t]:\n",
    "                        # 向下\n",
    "                        index = (t + grid[i][j]) % k\n",
    "                        dp[i][j][index] += dp[i-1][j][t]\n",
    "                        dp[i][j][index] %= self.MOD\n",
    "                    if j > 0 and dp[i][j-1][t]:\n",
    "                        # 向右\n",
    "                        index = (t + grid[i][j]) % k\n",
    "                        dp[i][j][index] += dp[i][j-1][t]\n",
    "                        dp[i][j][index] %= self.MOD\n",
    "        \n",
    "        return dp[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, nums: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, m = len(nums), len(nums[0])\n",
    "        f = [[[0] * k for _ in range(m)] for _ in range(n)]\n",
    "        f[0][0][nums[0][0] % k] = 1\n",
    "        for i in range(1, n):\n",
    "            for v in range(k):\n",
    "                f[i][0][(v + nums[i][0]) % k] += f[i - 1][0][v]\n",
    "        for i in range(1, m):\n",
    "            for v in range(k):\n",
    "                f[0][i][(v + nums[0][i]) % k] += f[0][i - 1][v]\n",
    "        for i in range(1, n):\n",
    "            for j in range(1, m):\n",
    "                for v in range(k):\n",
    "                    f[i][j][(nums[i][j] + v) % k] += f[i - 1][j][v] + f[i][j - 1][v]\n",
    "                    f[i][j][(nums[i][j] + v) % k] %= MOD\n",
    "        return f[n - 1][m - 1][0] % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mod = 10**9 + 7\n",
    "        # [[[0] * 9 for _ in range(0, 3)] for _ in range(0, 3)]\n",
    "        dp = [[[0] * k for _ in range(n)] for _ in range(m)]\n",
    "        # 先求出0列所有的值\n",
    "        modVal = grid[0][0] % k\n",
    "        dp[0][0][modVal] = 1\n",
    "        for i in range(1, m):\n",
    "            modVal = (modVal + grid[i][0] % k) % k\n",
    "            dp[i][0][modVal] = 1\n",
    "        #再求出0行所有的值 \n",
    "        modVal = grid[0][0] % k\n",
    "        for j in range(1, n):\n",
    "            modVal = (modVal + grid[0][j] % k) % k\n",
    "            dp[0][j][modVal] = 1\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                # 算出 dp[i - 1][j], dp[i][j - 1] 里包含的所有mod值\n",
    "                for x in range(k):\n",
    "                    a, b = dp[i - 1][j][x], dp[i][j - 1][x]\n",
    "                    x_mod = (x + grid[i][j] % k) % k\n",
    "                    dp[i][j][x_mod]+=a\n",
    "                    dp[i][j][x_mod]+=b\n",
    "                    dp[i][j][x_mod]%=mod\n",
    "        return dp[m - 1][n - 1][0] if dp[m - 1][n - 1][0] >= 0 else 0"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, nums: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        n, m = len(nums), len(nums[0])\n",
    "        f = [[[0] * k for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "        f[1][0][0] = 1\n",
    "        for i in range(1, n + 1):\n",
    "            for j in range(1, m + 1):\n",
    "                for v in range(k):\n",
    "                    f[i][j][v] = f[i - 1][j][(v + nums[i - 1][j - 1]) % k] + f[i][j - 1][(v + nums[i - 1][j - 1]) % k]\n",
    "                    f[i][j][v] %= MOD\n",
    "        return f[n][m][0] % MOD\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0] * k for k2 in range(n)] for k1 in range(m)]\n",
    "        \n",
    "        MOD = 10 ** 9 + 7\n",
    "        x = grid[0][0]\n",
    "        dp[0][0][x % k] = 1\n",
    "\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                x=grid[i][j]\n",
    "                for v in range(k):\n",
    "                    if i>=1:\n",
    "                        dp[i][j][v]=(dp[i][j][v]+dp[i-1][j][(v+k-x)%k])%MOD\n",
    "                    if j >=1:\n",
    "                        dp[i][j][v]=(dp[i][j][v]+dp[i][j-1][(v+k-x)%k])%MOD\n",
    "\n",
    "        return dp[m-1][n-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        mod = 10 ** 9 + 7\n",
    "        dp = [[[0] * k for _ in range(n)] for _ in range(m)]\n",
    "        \n",
    "        dp[0][0][grid[0][0] % k] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for l in range(k):\n",
    "                    if i > 0:\n",
    "                        dp[i][j][l] += dp[i - 1][j][(l - grid[i][j] + k) % k]\n",
    "                    if j > 0:\n",
    "                        dp[i][j][l] += dp[i][j - 1][(l - grid[i][j] + k) % k]\n",
    "                    dp[i][j][l] %= mod\n",
    "                # print(i, j, dp[i][j])\n",
    "        # print(dp)\n",
    "        return dp[m - 1][n - 1][0]\n",
    "#         @cache\n",
    "#         def dfs(i, j, l):\n",
    "#             if i == 0 and j == 0 and l == grid[i][j] % k:\n",
    "#                 return 1\n",
    "#             cnt = 0\n",
    "#             if i > 0:\n",
    "#                 cnt += dfs(i - 1, j, (l - grid[i][j] + k) % k)\n",
    "#             if j > 0:\n",
    "#                 cnt += dfs(i, j - 1, (l - grid[i][j] + k) % k)\n",
    "#             return cnt % mod\n",
    "        \n",
    "#         return dfs(m - 1, n - 1, 0)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mod=int(1e9+7)\n",
    "        def ok(x,y):\n",
    "            if x>=0 and x<m and y>=0 and y<n:\n",
    "                return True\n",
    "            return False\n",
    "        dp=[[[0 for _ in range(k)] for _ in range(n+1)] for _ in range(m+1)]\n",
    "        dp[0][1][0]=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for v in range(k):\n",
    "                    dp[i+1][j+1][(v+grid[i][j])%k]=(dp[i][j+1][v]+dp[i+1][j][v])%mod\n",
    "        return dp[m][n][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0] * k for _ in range(n)] for _ in range(m)]\n",
    "        dp[m - 1][n - 1][grid[m - 1][n - 1] % k] = 1\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for r in range(k):\n",
    "                dp[i][n - 1][r] = dp[i + 1][n - 1][(k + r - grid[i][n - 1] % k) % k]\n",
    "        for j in range(n - 2, -1, -1):\n",
    "            for r in range(k):\n",
    "                dp[m - 1][j][r] = dp[m - 1][j + 1][(k + r - grid[m - 1][j] % k) % k]\n",
    "        for i in range(m - 2, -1, -1):\n",
    "            for j in range(n - 2, - 1, -1):\n",
    "                for r in range(k):\n",
    "                    need = (k + r - grid[i][j] % k) % k\n",
    "                    dp[i][j][r] = (dp[i + 1][j][need] + dp[i][j + 1][need]) % MOD\n",
    "        return dp[0][0][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        mod=int(1e9+7)\n",
    "        def ok(x,y):\n",
    "            if x>=0 and x<m and y>=0 and y<n:\n",
    "                return True\n",
    "            return False\n",
    "        dp=[[[0 for _ in range(k)] for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0][grid[0][0]%k]=1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for v in range(k):\n",
    "                    if i==0 and j==0:\n",
    "                        continue\n",
    "                    elif i==0:\n",
    "                        dp[i][j][(v+grid[i][j])%k]=dp[i][j-1][v]%mod\n",
    "                    elif j==0:\n",
    "                        dp[i][j][(v+grid[i][j])%k]=dp[i-1][j][v]%mod\n",
    "                    else:\n",
    "                        dp[i][j][(v+grid[i][j])%k]=(dp[i-1][j][v]+dp[i][j-1][v])%mod\n",
    "        return dp[m-1][n-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        f = [ [[ 0 for _ in range(k)] for _ in range(n)] for _ in range(m)]\n",
    "        f[m - 1][n - 1][grid[m-1][n-1] % k] = 1\n",
    "        for i in range(m - 1, -1, -1):\n",
    "            for j in range(n - 1, -1, -1):\n",
    "                for d in range(k):\n",
    "                    if i == m - 1 and j == n - 1:\n",
    "                        continue\n",
    "                    if i == m - 1:\n",
    "                        f[i][j][(d + grid[i][j]) % k] = f[i][j+1][d] % MOD\n",
    "                        continue\n",
    "                    if j == n - 1:\n",
    "                        f[i][j][(d + grid[i][j]) % k] = f[i+1][j][d] % MOD\n",
    "                        continue\n",
    "                    f[i][j][(d + grid[i][j]) % k] = (f[i+1][j][d] + f[i][j+1][d]) % MOD\n",
    "        return f[0][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mod = 10**9 + 7\n",
    "        # @cache\n",
    "        # def dfs(i, j, pre_sum):\n",
    "        #     # 先判断边界，再处理数据\n",
    "        #     if i >= m or j >= n:\n",
    "        #         return 0\n",
    "        #     pre_sum = (pre_sum + grid[i][j]) % k\n",
    "        #     if i == m-1 and j == n-1:\n",
    "        #         return 1 if pre_sum == 0 else 0\n",
    "        #     return (dfs(i + 1, j, pre_sum) + dfs(i, j + 1, pre_sum)) % mod\n",
    "        \n",
    "        # ans = dfs(0, 0, 0)\n",
    "        # dfs.cache_clear\n",
    "        # return ans\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i, j, v):\n",
    "        #     if i < 0 or j < 0:\n",
    "        #         return 0\n",
    "        #     v = (v + grid[i][j]) % k\n",
    "        #     if i == j == 0:\n",
    "        #         return 1 if v == 0 else 0\n",
    "        #     return (dfs(i-1, j, v) + dfs(i, j-1, v)) % mod\n",
    "        # ans = dfs(m-1, n-1, 0)\n",
    "        # dfs.cache_clear() # 不加会超出内存限制\n",
    "        # return ans\n",
    "\n",
    "        # f[i+1][j+1][v] += f[i][j+1][(v+k-grid[i][j])%k] + f[i+1][j][(v+k-grid[i][j])%k] # 查表法\n",
    "        # f[i+1][j+1][(v+grid[i][j])%k] += f[i][j+1][v] + f[i+1[j][v]] # 刷表法\n",
    "        f = [[[0] * k for _ in range(n+1)] for _ in range(m+1)]\n",
    "        f[0][1][0] = 1 # 等价于 f[1][0][0] = 1 f[1][1][grid[0][0]%k]=1\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    f[i+1][j+1][(v+grid[i][j])%k] += f[i][j+1][v] + f[i+1][j][v]\n",
    "                    f[i+1][j+1][(v+grid[i][j])%k] %= mod\n",
    "        return f[-1][-1][0]\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD=10**9+7\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[[0]*50 for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0][grid[0][0]%k]=1\n",
    "        pre=grid[0][0]%k\n",
    "        for j in range(1,n):\n",
    "            pre=(pre+grid[0][j])%k\n",
    "            dp[0][j][pre]=1\n",
    "        pre=grid[0][0]%k\n",
    "        for i in range(1,m):\n",
    "            pre=(pre+grid[i][0])%k\n",
    "            dp[i][0][pre]=1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                for t in range(k):\n",
    "                    dp[i][j][(t+grid[i][j])%k]=(dp[i-1][j][t]+dp[i][j-1][t])%MOD\n",
    "        return dp[m-1][n-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        \n",
    "        mod=10**9+7\n",
    "        \n",
    "        dp=[[0]*n for i in range(m)]\n",
    "        \n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                dp[i][j]=[0]*k\n",
    "        \n",
    "        for i in range(k):\n",
    "            dp[0][0][i]=1 if grid[0][0]%k==i else 0\n",
    "        \n",
    "        # dp[0][0][]=\n",
    "        \n",
    "        for i in range(1,m):\n",
    "            \n",
    "            for j in range(k):\n",
    "                dp[i][0][j]=1 if dp[i-1][0][(j-grid[i][0])%k] else 0\n",
    "                \n",
    "        for i in range(1,n):\n",
    "            for j in range(k):\n",
    "                dp[0][i][j]=1 if dp[0][i-1][(j-grid[0][i])%k] else 0\n",
    "                \n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                for kk in range(k):\n",
    "                    \n",
    "                    dp[i][j][kk]=(dp[i-1][j][(kk-grid[i][j])%k]+dp[i][j-1][(kk-grid[i][j])%k])%mod\n",
    "            \n",
    "            \n",
    "            \n",
    "            \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        return dp[-1][-1][0]%mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp = [[[0 for _ in range(k)] for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0][grid[0][0] % k] = 1\n",
    "        mod = 1000000007\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for v in range(k):\n",
    "                    d = (v + grid[i][j]) % k\n",
    "                    dp[i][j][d] = (dp[i][j][d] +  (dp[i][j-1][v] if j-1 >= 0 else 0)) % mod\n",
    "                    dp[i][j][d] = (dp[i][j][d] +  (dp[i-1][j][v] if i-1 >= 0 else 0)) % mod\n",
    "        return dp[m-1][n-1][0] \n",
    "            \n",
    "s = Solution()\n",
    "s.numberOfPaths([[5,2,4],[3,0,5],[0,7,2]],3)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        MOD = 10 ** 9 + 7\n",
    "        dp = [[[0] * k for _ in range(m + 1)] for _ in range(n + 1)]\n",
    "        dp[0][1][0] = 1\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(m):\n",
    "                for q in range(k):\n",
    "                    dp[i + 1][j + 1][(q + grid[i][j]) % k] += (dp[i][j + 1][q] + dp[i + 1][j][q]) % MOD\n",
    "        return dp[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        f[0][1][0] = 1\n",
    "        for i, row in enumerate(grid):\n",
    "            for j, x in enumerate(row):\n",
    "                for v in range(k):\n",
    "                    f[i + 1][j + 1][(v + x) % k] = (f[i + 1][j][v] + f[i][j + 1][v]) % MOD\n",
    "        return f[m][n][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        lll=10**9+7\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        if k==1:\n",
    "            dp=[[0 for _ in range(n)] for _ in range(m)]\n",
    "            dp[0][0]=1\n",
    "            for i in range(m):\n",
    "                for j in range(n):\n",
    "                    if i!=0 and j!=0:\n",
    "                        dp[i][j]+=dp[i-1][j]+dp[i][j-1]\n",
    "                    elif i!=0:\n",
    "                        dp[i][j]+=dp[i-1][j]\n",
    "                    elif j!=0:\n",
    "                        dp[i][j]+=dp[i][j-1]\n",
    "            #print(dp)\n",
    "            return dp[-1][-1]%lll\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                grid[i][j]=grid[i][j]%k\n",
    "        dp=[[[0 for _ in range(k)] for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0][grid[0][0]]=1\n",
    "        for i in range(1,n):\n",
    "            for l in range(k):\n",
    "                tp=(k-grid[0][i]+l)%k  \n",
    "                #print(k,l,tp,grid[0][i])\n",
    "                dp[0][i][l]+=dp[0][i-1][tp]\n",
    "        #print(dp)\n",
    "        for i in range(1,m):\n",
    "            for l in range(k):\n",
    "                #print(k,grid[i][0],l,tp)\n",
    "                tp=(k-grid[i][0]+l)%k  \n",
    "                dp[i][0][l]+=dp[i-1][0][tp] \n",
    "        #print(dp)\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                for l in range(k):\n",
    "                    tp=(k-grid[i][j]+l)%k\n",
    "                    dp[i][j][l]+=dp[i-1][j][tp]+dp[i][j-1][tp]\n",
    "                    dp[i][j][l]%=lll\n",
    "        #print(dp)\n",
    "        return dp[-1][-1][0]%lll"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 1000000007 \n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[[0 for _ in range(k)] for _ in range(m)] for _ in range(n)]\n",
    "        dp[n-1][m-1][grid[n-1][m-1]%k] = 1\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for r in range(k):\n",
    "                dp[i][m-1][r] = dp[i+1][m-1][(k+r-(grid[i][m-1]%k))%k]\n",
    "        for j in range(m-2,-1,-1):\n",
    "            for r in range(k):\n",
    "                dp[n-1][j][r] = dp[n-1][j+1][(k+r-(grid[n-1][j]%k))%k]\n",
    "        for i in range(n-2,-1,-1):\n",
    "            for j in range(m-2,-1,-1):\n",
    "                for r in range(k):\n",
    "                    need = (k+r-(grid[i][j]%k))%k                \n",
    "                    dp[i][j][r] = dp[i+1][j][need]             \n",
    "                    dp[i][j][r] = (dp[i][j][r]+dp[i][j+1][need])%mod                        \n",
    "        return dp[0][0][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 10**9+7\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        mat = [[[0 for t in range(k+1)] for j in range(n)] for i in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                if i==0 :\n",
    "                    if j==0:\n",
    "                        mat[i][j][-1] = grid[i][j]%k\n",
    "                        mat[i][j][mat[i][j][-1]%k] = 1\n",
    "                    else:\n",
    "                        mat[i][j][-1] = (mat[i][j-1][-1]+grid[i][j])%k\n",
    "                        mat[i][j][mat[i][j][-1]%k] = 1\n",
    "                else:\n",
    "                    if j==0:\n",
    "                        mat[i][j][-1] = (mat[i-1][j][-1]+grid[i][j])%k\n",
    "                        mat[i][j][mat[i][j][-1]%k] = 1\n",
    "                    else:\n",
    "                        arr = [(mat[i-1][j][t]+mat[i][j-1][t])%mod for t in range(k)]\n",
    "                        per = grid[i][j]%k # 偏移量\n",
    "                        arr = arr[k-per:] + arr[:k-per]\n",
    "                        mat[i][j] = arr\n",
    "        return mat[-1][-1][0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 1e9 + 7\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[[0]*k for _ in range(m)] for _ in range(n)]\n",
    "        dp[n-1][m-1][grid[n-1][m-1] % k] = 1\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for r in range(k):\n",
    "                dp[i][m-1][r] = dp[i+1][m-1][(k+r-grid[i][m-1]%k)%k]\n",
    "        for i in range(m-2, -1, -1):\n",
    "            for r in range(k):\n",
    "                dp[n-1][i][r] = dp[n-1][i+1][(k+r-grid[n-1][i]%k)%k]\n",
    "        for i in range(n-2, -1, -1):\n",
    "            for j in range(m-2, -1, -1):\n",
    "                for r in range(k):\n",
    "                    need = (k + r - grid[i][j] % k) % k\n",
    "                    dp[i][j][r] = dp[i+1][j][need]\n",
    "                    dp[i][j][r] = (dp[i][j][r] + dp[i][j+1][need]) % mod\n",
    "        return int(dp[0][0][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, G: List[List[int]], k: int) -> int:\n",
    "        mod=1e9+7\n",
    "        m, n = len(G), len(G[0])\n",
    "        dp = [[0]*k for _ in range(n + 1)]; \n",
    "        dp[0][0] = 1\n",
    "        for i, j in product(range(m), range(n)): \n",
    "            t = [(x+y) % mod for x,y in zip(dp[j],dp[j-1])]\n",
    "            d = G[i][j] % k\n",
    "            dp[j] = t[d:] + t[:d]\n",
    "        return int(dp[n-1][0])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        # dp[i][j][remain]到达i,j这个点路径和且%k榆树为remain的路径个数\n",
    "        # dp[m-1][n-1][0]\n",
    "        # dp[i][j][remain]=dp[i-1][j][(remain-grid[i][j])%k]+dp[i][j-1][(remain-grid[i][j])%k]\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        Mod=10**9+7\n",
    "        dp=[[[0]* k for _ in range(n)]for _ in range(m)]\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for r in range(k):\n",
    "                    if i==0 and j==0:\n",
    "                        dp[i][j][grid[0][0]%k]=1\n",
    "                    elif i==0:\n",
    "                        dp[i][j][r]=dp[i][j-1][(r-grid[i][j])%k]\n",
    "                    elif j==0:\n",
    "                        dp[i][j][r]=dp[i-1][j][(r-grid[i][j])%k]\n",
    "                    else:\n",
    "                        dp[i][j][r]=dp[i-1][j][(r-grid[i][j])%k]+dp[i][j-1][(r-grid[i][j])%k]\n",
    "        return dp[m-1][n-1][0]%Mod\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0] * k for _ in range(n + 1)] for _ in range(m + 1)]\n",
    "        \n",
    "        dp[1][0][0] = 1\n",
    "        for i in range(1, m + 1):\n",
    "            for j in range(1, n + 1):\n",
    "                cur = grid[i - 1][j - 1] % k\n",
    "                for p in range(k):\n",
    "                    dp[i][j][p] += dp[i - 1][j][(p - cur) % k] + dp[i][j - 1][(p - cur) % k]\n",
    "        \n",
    "        return dp[m][n][0] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0]*k for _ in range(n)] for _ in range(m)]\n",
    "        dp[m-1][n-1][(k-grid[-1][-1]) % k] = 1\n",
    "        for x in range(m-1, -1, -1):\n",
    "            for y in range(n-1, -1, -1):\n",
    "                for yu in range(k-1, -1, -1):\n",
    "                    if x < m-1:\n",
    "                        dp[x][y][yu] = dp[x+1][y][(yu+grid[x][y]) % k]\n",
    "                    if y < n-1:\n",
    "                        dp[x][y][yu] += dp[x][y+1][(yu+grid[x][y]) % k]\n",
    "        return dp[0][0][0] % (10**9+7)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        f = [[[0]*k for _j in range(n)] for _i in range(m)]\n",
    "        f[0][0][grid[0][0]%k] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for r in range(k):\n",
    "                    if i>=1:\n",
    "                        f[i][j][(r+grid[i][j]) % k] += f[i-1][j][r]\n",
    "                    if j>=1:\n",
    "                        f[i][j][(r+grid[i][j]) % k] += f[i][j-1][r]\n",
    "        \n",
    "        rst = f[-1][-1][0] % 1000000007\n",
    "        return rst"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        dp=[[[0]*k for j in range(n)] for i in range(m)]\n",
    "       # print(len(dp),len(dp[0]))\n",
    "        dp[0][0][grid[0][0]%k]=1\n",
    "        s=grid[0][0]\n",
    "        for i in range(1,n):\n",
    "            s+=grid[0][i]\n",
    "            dp[0][i][s%k]=1\n",
    "        s=grid[0][0]\n",
    "        for j in range(1,m):\n",
    "            s+=grid[j][0]\n",
    "            dp[j][0][s%k]=1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                for p in range(k):\n",
    "                    dp[i][j][p]=dp[i-1][j][p-grid[i][j]%k]+dp[i][j-1][p-grid[i][j]%k]\n",
    "        return dp[m-1][n-1][0]%(10**9+7)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "\n",
    "        mod = 10 ** 9 + 7\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        dp = [[[0] * k for _ in range(n)] for _ in range(m)]\n",
    "        s = 0\n",
    "        for i in range(m):\n",
    "            s += grid[i][0]\n",
    "            dp[i][0][s % k] = 1\n",
    "        \n",
    "        s = 0\n",
    "        for i in range(n):\n",
    "            s += grid[0][i]\n",
    "            dp[0][i][s % k] = 1\n",
    "\n",
    "        for i in range(1, m):\n",
    "            for j in range(1, n):\n",
    "                cur = grid[i][j] % k\n",
    "                for p in range(k):\n",
    "                    dp[i][j][p] += dp[i - 1][j][(p - cur) % k] + dp[i][j - 1][(p - cur) % k]\n",
    "        \n",
    "        return dp[m - 1][n - 1][0] % mod"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp = [[[0]*k for j in range(n+1)] for i in range(m+1)]\n",
    "        dp[0][1][0] = 1\n",
    "        for i in range(m):\n",
    "            for j in range(n):\n",
    "                for t in range(k):\n",
    "                    dp[i+1][j+1][(t+grid[i][j])%k] += dp[i][j+1][t]\n",
    "                    dp[i+1][j+1][(t+grid[i][j])%k] += dp[i+1][j][t]\n",
    "        # for l in dp: print(l)\n",
    "        return dp[-1][-1][0] % 1000000007"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MOD = 10**9+7\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp = [[[0]*k for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0][grid[0][0]%k] = 1\n",
    "        psum = grid[0][0]\n",
    "        for j in range(1,n):\n",
    "            psum += grid[0][j]\n",
    "            dp[0][j][psum%k] = 1\n",
    "        psum = grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            psum += grid[i][0]\n",
    "            dp[i][0][psum%k] = 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                cur = grid[i][j]%k\n",
    "                for p in range(k):\n",
    "                    dp[i][j][(cur+p)%k] = dp[i-1][j][p]+dp[i][j-1][p]\n",
    "        return dp[-1][-1][0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        # 记录每个位置，除k之后不同余数的路径数目\n",
    "        MOD = 10**9+7\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp = [[[0]*k for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0][grid[0][0]%k] = 1\n",
    "        psum = grid[0][0]\n",
    "        for j in range(1,n):\n",
    "            psum += grid[0][j]\n",
    "            dp[0][j][psum%k] = 1\n",
    "        psum = grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            psum += grid[i][0]\n",
    "            dp[i][0][psum%k] = 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                cur = grid[i][j]%k\n",
    "                for p in range(k):\n",
    "                    dp[i][j][(cur+p)%k] = dp[i-1][j][p]+dp[i][j-1][p]\n",
    "        return dp[-1][-1][0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        # 记录每个位置，除k之后不同余数的路径数目\n",
    "        MOD = 10**9+7\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        dp = [[[0]*k for _ in range(n)] for _ in range(m)]\n",
    "        dp[0][0][grid[0][0]%k] = 1\n",
    "        psum = grid[0][0]\n",
    "        for j in range(1,n):\n",
    "            psum += grid[0][j]\n",
    "            dp[0][j][psum%k] = 1\n",
    "        psum = grid[0][0]\n",
    "        for i in range(1,m):\n",
    "            psum += grid[i][0]\n",
    "            dp[i][0][psum%k] = 1\n",
    "        for i in range(1,m):\n",
    "            for j in range(1,n):\n",
    "                cur = grid[i][j]%k\n",
    "                for p in range(k):\n",
    "                    dp[i][j][(cur+p)%k] = dp[i-1][j][p]+dp[i][j-1][p]\n",
    "        return dp[-1][-1][0]%MOD"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 1000000007 \n",
    "        def f(grid,n,m,k,i,j,r,dp):\n",
    "            if i==n-1 and j==m-1:\n",
    "                return 1 if grid[i][j]%k==r else 0\n",
    "            if dp[i][j][r]!=-1:\n",
    "                return dp[i][j][r]\n",
    "            need = (k+r-(grid[i][j]%k))%k\n",
    "            ans = 0\n",
    "            if i+1<n:\n",
    "                ans = f(grid,n,m,k,i+1,j,need,dp)\n",
    "            if j+1<m:\n",
    "                ans = (ans+f(grid,n,m,k,i,j+1,need,dp))%mod\n",
    "            dp[i][j][r] = ans\n",
    "            return ans\n",
    "        #n*m*k+1\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[[-1 for _ in range(k)] for _ in range(m)] for _ in range(n)]\n",
    "        return f(grid,n,m,k,0,0,0,dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        def f(grid,n,m,k,i,j,r,dp):\n",
    "            if i==n-1 and j==m-1:\n",
    "                return 1 if grid[i][j]%k==r else 0\n",
    "            if dp[i][j][r]!=-1:\n",
    "                return dp[i][j][r]\n",
    "            need = (k+r-(grid[i][j]%k))%k\n",
    "            ans = 0\n",
    "            if i+1<n:\n",
    "                ans = f(grid,n,m,k,i+1,j,need,dp)\n",
    "            if j+1<m:\n",
    "                ans = (ans+f(grid,n,m,k,i,j+1,need,dp))%1000000007\n",
    "            dp[i][j][r] = ans\n",
    "            return ans\n",
    "        #n*m*k+1\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[[-1 for _ in range(k)] for _ in range(m)] for _ in range(n)]\n",
    "        return f(grid,n,m,k,0,0,0,dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 1000000007 \n",
    "        def f(grid,n,m,k,i,j,r,dp):\n",
    "            nonlocal mod\n",
    "            if i==n-1 and j==m-1:\n",
    "                return 1 if grid[i][j]%k==r else 0\n",
    "            if dp[i][j][r]!=-1:\n",
    "                return dp[i][j][r]\n",
    "            need = (k+r-(grid[i][j]%k))%k\n",
    "            ans = 0\n",
    "            if i+1<n:\n",
    "                ans = f(grid,n,m,k,i+1,j,need,dp)\n",
    "            if j+1<m:\n",
    "                ans = (ans+f(grid,n,m,k,i,j+1,need,dp))%mod\n",
    "            dp[i][j][r] = ans\n",
    "            return ans\n",
    "        #n*m*k+1\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[[-1 for _ in range(k)] for _ in range(m)] for _ in range(n)]\n",
    "        return f(grid,n,m,k,0,0,0,dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 1000000007 \n",
    "        def f(grid,n,m,k,i,j,r,dp):\n",
    "            if i==n-1 and j==m-1:\n",
    "                return 1 if grid[i][j]%k==r else 0\n",
    "            if dp[i][j][r]!=-1:\n",
    "                return dp[i][j][r]\n",
    "            need = (k+r-(grid[i][j]%k))%k\n",
    "            ans = 0\n",
    "            if i+1<n:\n",
    "                ans = f(grid,n,m,k,i+1,j,need,dp)\n",
    "            if j+1<m:\n",
    "                ans = (ans+f(grid,n,m,k,i,j+1,need,dp))%mod\n",
    "            dp[i][j][r] = ans\n",
    "            return ans\n",
    "        #n*m*k+1\n",
    "        n = len(grid)\n",
    "        m = len(grid[0])\n",
    "        dp = [[[-1 for _ in range(k)] for _ in range(m)] for _ in range(n)]\n",
    "        return f(grid,n,m,k,0,0,0,dp)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "mod = 10**9+7\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(i, j):\n",
    "            xx = grid[i][j]\n",
    "            res = [0]*k\n",
    "            if i == m-1 and j == n-1:\n",
    "                res[xx%k] += 1\n",
    "                return res\n",
    "            \n",
    "            for x, y in [[i+1, j], [i, j+1]]:\n",
    "                if 0<=x<m and 0<=y<n:\n",
    "                    cur = dfs(x, y)\n",
    "                    for j in range(k):\n",
    "                        res[(xx+j)%k] += cur[j]\n",
    " \n",
    "            return [num%mod for num in res]\n",
    "        \n",
    "        return dfs(0, 0)[0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        cache = [[None for _ in range(n)] for _ in range(m)]\n",
    "\n",
    "        cache[0][0] = [0 for _ in range(k)]\n",
    "        cache[0][0][grid[0][0]%k] = 1\n",
    "\n",
    "        def search(m_,n_):\n",
    "            if m_<0 or n_<0:\n",
    "                return None\n",
    "            elif cache[m_][n_] is not None:\n",
    "                return cache[m_][n_]\n",
    "            else:\n",
    "                tmp = [0 for _ in range(k)]\n",
    "                v = grid[m_][n_]\n",
    "\n",
    "                last = search(m_-1,n_)\n",
    "                if last:\n",
    "                    for i in range(k):\n",
    "                        idx = (i+v)%k\n",
    "                        tmp[idx]+=last[i]\n",
    "\n",
    "                last = search(m_,n_-1)\n",
    "                if last:\n",
    "                    for i in range(k):\n",
    "                        idx = (i+v)%k\n",
    "                        tmp[idx]+=last[i]  \n",
    "\n",
    "                cache[m_][n_] = [x%(10**9+7) for x in tmp]\n",
    "                return  tmp\n",
    "        \n",
    "        search(m-1,n-1)\n",
    "        return cache[-1][-1][0]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        MAXNUM = 1000000007\n",
    "        dp = {}\n",
    "        rownum = len(grid)\n",
    "        colnum = len(grid[0])\n",
    "        dp[(0, 0, grid[0][0]%k)] = 1\n",
    "        for x in range(rownum):\n",
    "            for y in range(colnum):\n",
    "                for step in range(k):\n",
    "                    if dp.get((x, y, step)) != None:\n",
    "                        if x+1<rownum:\n",
    "                            nxtmod = (step+grid[x+1][y])%k\n",
    "                            if dp.get((x+1, y, nxtmod)) == None:\n",
    "                                dp[(x+1, y, nxtmod)] = 0\n",
    "                            dp[(x+1, y, nxtmod)] = (dp[(x+1, y, nxtmod)] + dp.get((x, y, step))) % MAXNUM\n",
    "                        if y+1<colnum:\n",
    "                            nxtmod = (step+grid[x][y+1])%k\n",
    "                            if dp.get((x, y+1, nxtmod)) == None:\n",
    "                                dp[(x, y+1, nxtmod)] = 0\n",
    "                            dp[(x, y+1, nxtmod)] = (dp[(x, y+1, nxtmod)] + dp.get((x, y, step))) % MAXNUM\n",
    "        # print(dp)\n",
    "        if dp.get((rownum-1, colnum-1, 0)) == None:\n",
    "            return 0\n",
    "        else:\n",
    "            return dp.get((rownum-1, colnum-1, 0))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(x: int, y: int, d: int) -> int:\n",
    "            if x == 0 and y == 0:\n",
    "                # print(f'd:{d}')\n",
    "                return int(grid[0][0] % k == d)\n",
    "            res = 0\n",
    "            nd = (d - grid[x][y]) % k\n",
    "            # nd = (d + grid[x][y]) % k\n",
    "            if x - 1 >= 0:\n",
    "                res += dfs(x - 1, y, nd)\n",
    "            if y - 1 >= 0:\n",
    "                res += dfs(x, y - 1, nd)\n",
    "            # print(f'x:{x},y:{y},res:{res}')\n",
    "            return res % mod\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = dfs(m - 1, n - 1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(x: int, y: int, d: int) -> int:\n",
    "            if x == 0 and y == 0:\n",
    "                # print(f'd:{d}')\n",
    "                return int(grid[0][0] % k == d)\n",
    "            res = 0\n",
    "            nd = (d - grid[x][y] + k) % k\n",
    "            if x - 1 >= 0:\n",
    "                res += dfs(x - 1, y, nd)\n",
    "            if y - 1 >= 0:\n",
    "                res += dfs(x, y - 1, nd)\n",
    "            # print(f'x:{x},y:{y},res:{res}')\n",
    "            return res % mod\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = dfs(m - 1, n - 1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue,Queue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(x:int,y:int,v:int)->int:\n",
    "            v = (v + grid[x][y]) % k\n",
    "            if x == m-1 and y == n-1:\n",
    "                return 1 if v == 0 else 0\n",
    "            res = 0\n",
    "            if x + 1 < m:\n",
    "                res += dfs(x+1,y,v)\n",
    "            if y + 1 < n:\n",
    "                res += dfs(x,y+1,v)\n",
    "            return res % 1000000007\n",
    "        ans =  dfs(0,0,0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mod = 10**9 + 7\n",
    "        # @cache\n",
    "        # def dfs(i, j, pre_sum):\n",
    "        #     if i == m-1 and j == n-1 and pre_sum % k == 0:\n",
    "        #         return 1\n",
    "        #     if i >= m or j >= n:\n",
    "        #         return 0\n",
    "        #     pre_sum = (pre_sum + grid[i][j]) % k\n",
    "        #     return (dfs(i + 1, j, pre_sum) + dfs(i, j + 1, pre_sum)) % mod\n",
    "        \n",
    "        # return dfs(0, 0, 0)\n",
    "\n",
    "        @cache\n",
    "        def dfs(i, j, v):\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            v = (v + grid[i][j]) % k\n",
    "            if i == j == 0:\n",
    "                return 1 if v == 0 else 0\n",
    "            return (dfs(i-1, j, v) + dfs(i, j-1, v)) % mod\n",
    "        ans = dfs(m-1, n-1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(i: int, j: int, v: int) -> int:\n",
    "            if i < 0 or j < 0:\n",
    "                return 0\n",
    "            v = (v + grid[i][j]) % k\n",
    "            if i == j == 0:\n",
    "                if v == 0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0\n",
    "            return (dfs(i-1, j, v) + dfs(i, j-1, v)) % mod\n",
    "        ans = dfs(m-1, n-1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        res = 0\n",
    "        mod = 10**9+7\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        @lru_cache(None)\n",
    "        def dfs(row, col, left):\n",
    "            nonlocal res, k, n, m\n",
    "            if row==n:return 0 \n",
    "            if col==m:return 0 \n",
    "            if row==n-1 and col==m-1:\n",
    "                if (left+grid[row][col])%k==0:\n",
    "                    return 1\n",
    "                else:\n",
    "                    return 0 \n",
    "            left=(left+grid[row][col])%k\n",
    "            \n",
    "            \n",
    "            return (dfs(row+1, col, left)+dfs(row, col+1, left))%mod\n",
    "\n",
    "        res = dfs(0,0,0)\n",
    "        dfs.cache_clear()\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        Mod = 1_000_000_007\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "\n",
    "        @cache\n",
    "        def choose_direction(_m, _n, _sum):\n",
    "            if _m < 0 or _n < 0:\n",
    "                return 0\n",
    "            if _m == 0 and _n == 0:\n",
    "                return 1 if _sum % k == 0 else 0\n",
    "            return (choose_direction(_m - 1, _n, (_sum + grid[_m - 1][_n]) % k) + choose_direction(_m, _n - 1, (_sum + grid[_m][_n - 1]) % k)) % Mod\n",
    "\n",
    "        res = choose_direction(m - 1, n - 1, grid[m - 1][n - 1])\n",
    "        choose_direction.cache_clear()\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod = 10 ** 9 + 7\n",
    "        @cache\n",
    "        def dfs(x: int, y: int, d: int) -> int:\n",
    "            if x < 0 or y < 0:\n",
    "                return 0\n",
    "            nd = (d + grid[x][y]) % k\n",
    "            if x == 0 and y == 0:\n",
    "                return int(nd == 0)\n",
    "            return (dfs(x - 1, y, nd) + dfs(x, y - 1, nd)) % mod\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = dfs(m - 1, n - 1, 0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    \n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        mod=10**9+7\n",
    "        n=len(grid)\n",
    "        m=len(grid[0])\n",
    "        @cache\n",
    "        def dfs(i,j,v):\n",
    "            if i<0 or j<0:\n",
    "                return 0\n",
    "            v=(v+grid[i][j])%k\n",
    "            if i==0 and j==0:\n",
    "                return v%k==0\n",
    "            return (dfs(i-1,j,v)+dfs(i,j-1,v))%mod\n",
    "        \n",
    "        ans=int(dfs(n-1,m-1,0))\n",
    "        dfs.cache_clear()\n",
    "        return ans\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        mod = 1000000007\n",
    "\n",
    "        @cache\n",
    "        def dfs(i,j,t):\n",
    "            if i == 0 and j == 0: return 1 if t == grid[0][0] % k else 0\n",
    "            if i < 0 or j < 0: return 0\n",
    "            t = (t-grid[i][j]) % k\n",
    "            return (dfs(i,j-1,t) + dfs(i-1,j,t)) % mod\n",
    "\n",
    "        ans = dfs(m-1,n-1,0)\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        \n",
    "        MOD = 1_000_000_007\n",
    "        \n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        @cache\n",
    "        def dfs(i: int, j: int, w: int) -> int:\n",
    "            if i == m - 1 and j == n - 1:\n",
    "                return 1 if w % k == 0 else 0\n",
    "            \n",
    "            res = 0\n",
    "\n",
    "            if i + 1 < m:\n",
    "                res = (res + dfs(i + 1, j, (w + grid[i + 1][j]) % k)) % MOD\n",
    "\n",
    "            if j + 1 < n:\n",
    "                res = (res + dfs(i, j + 1, (w + grid[i][j + 1]) % k)) % MOD\n",
    "\n",
    "            return res\n",
    "\n",
    "        res = dfs(0, 0, grid[0][0])\n",
    "        \n",
    "        dfs.cache_clear()\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "kmod = 10**9 + 7\n",
    "class Solution:\n",
    "    def numberOfPaths(self, grid: List[List[int]], k: int) -> int:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        \n",
    "        @lru_cache(None)\n",
    "        def dfs(x, y, mod):\n",
    "            if (x, y) == (m - 1, n - 1):\n",
    "                return mod == 0\n",
    "            \n",
    "            res = 0\n",
    "            for dx, dy in ((0, 1), (1, 0)):\n",
    "                a, b = x + dx, y + dy\n",
    "                if 0 <= a < m and 0 <= b < n:\n",
    "                    res += dfs(a, b, (mod + grid[a][b]) % k)\n",
    "            return res % kmod\n",
    "\n",
    "        ans = dfs(0, 0, grid[0][0] % k) % kmod\n",
    "        dfs.cache_clear()\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        adjs = [0] * (n+1)\n",
    "        for a, b in corridors:\n",
    "            if a > b:\n",
    "                a,b = b, a \n",
    "            adjs[a] |= 1<<b\n",
    "\n",
    "        return sum((adjs[a] & adjs[b]).bit_count() for a, b in corridors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\r\n",
    "        bits = [0] * (n + 1)\r\n",
    "        for a, b in corridors:\r\n",
    "            if a > b: a, b = b, a\r\n",
    "            bits[a] += 1 << b\r\n",
    "        return sum((bits[a] & bits[b]).bit_count() for a, b in corridors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        adjs = [set() for _ in range(n+1)]\n",
    "        for a, b in corridors:\n",
    "            if a > b:\n",
    "                a,b = b, a \n",
    "            adjs[a].add(b)\n",
    "\n",
    "        return sum(len(adjs[a] & adjs[b]) for a, b in corridors)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        #given the undirected graph, we set directions to the graph to reduce search time\n",
    "        #going from undirected graph corridors to directed graph g\n",
    "        g = defaultdict(set)\n",
    "        for u, v in corridors:\n",
    "            if u < v:\n",
    "                g[u].add(v)\n",
    "            else:\n",
    "                g[v].add(u)\n",
    "\n",
    "        res = 0\n",
    "        for p1 in range(1, n + 1):\n",
    "            for p2 in g[p1]:\n",
    "                for p3 in g[p2]:\n",
    "                    if p3 in g[p1]:\n",
    "                        res += 1\n",
    "        return res\n",
    "    \n",
    "        # graph = defaultdict(set)\n",
    "        # for i, j in corridors:\n",
    "        #     graph[i].add(j)\n",
    "        #     graph[j].add(i)\n",
    "        \n",
    "        # ans = 0\n",
    "        # for i, j in corridors:\n",
    "        #     print(len(graph[i] & graph[j]))\n",
    "        #     ans += len(graph[i] & graph[j])\n",
    "        # return ans // 3\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # we go over all nodes and record cycles by it's sum of node values, and add it to result (a set), as if the total value are\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        #given the undirected graph, we set directions to the graph to reduce search time\n",
    "        #going from undirected graph corridors to directed graph g\n",
    "        g = defaultdict(set)\n",
    "        for u, v in corridors:\n",
    "            if u < v:\n",
    "                g[u].add(v)\n",
    "            else:\n",
    "                g[v].add(u)\n",
    "\n",
    "        res = 0\n",
    "        for p1 in range(1, n + 1):\n",
    "            for p2 in g[p1]:\n",
    "                for p3 in g[p2]:\n",
    "                    if p3 in g[p1]:\n",
    "                        res += 1\n",
    "        return res\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # we go over all nodes and record cycles by it's sum of node values, and add it to result (a set), as if the total value are\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for u, v in corridors:\n",
    "            if v > u:\n",
    "                g[u].add(v)\n",
    "            else:\n",
    "                g[v].add(u)\n",
    "        tot = 0\n",
    "        for x in range(1, n + 1):\n",
    "            for y in g[x]:\n",
    "                for z in g[x]:\n",
    "                    if z in g[y]:\n",
    "                        tot += 1\n",
    "\n",
    "        return tot \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        \"\"\"无向边定向减少枚举次数\"\"\"\n",
    "        adjMap = defaultdict(set)\n",
    "        for u, v in corridors:\n",
    "            if u < v:\n",
    "                adjMap[u].add(v)\n",
    "            else:\n",
    "                adjMap[v].add(u)\n",
    "\n",
    "        res = 0\n",
    "        for p1 in range(1, n + 1):\n",
    "            for p2 in adjMap[p1]:\n",
    "                for p3 in adjMap[p2]:\n",
    "                    if p3 in adjMap[p1]:\n",
    "                        res += 1\n",
    "        return res\n",
    "            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "\n",
    "# # combinations\n",
    "# 对每个点的邻居，两两配对看是否连接\n",
    "# 每个相同的环会重复统计 3 次，答案需除以 3。\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from itertools import combinations\n",
    "\n",
    "# 求无向图中长度为 3 的不同环的数量\n",
    "# 由于环的长度为 3，因此每个相同的环会重复统计 3 次，答案需除 3。\n",
    "class Solution1:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for u, v in corridors:\n",
    "            adj[u].add(v)\n",
    "            adj[v].add(u)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        # 对邻居两两判断\n",
    "        for p1 in range(1, n + 1):\n",
    "            for p2, p3 in combinations(adj[p1], 2):\n",
    "                if p2 in adj[p3]:\n",
    "                    res += 1\n",
    "\n",
    "        return res // 3\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        \"\"\"无向边定向减少枚举次数\"\"\"\n",
    "        adjMap = defaultdict(set)\n",
    "        for u, v in corridors:\n",
    "            if u < v:\n",
    "                adjMap[u].add(v)\n",
    "            else:\n",
    "                adjMap[v].add(u)\n",
    "\n",
    "        res = 0\n",
    "        for p1 in range(1, n + 1):\n",
    "            for p2 in adjMap[p1]:\n",
    "                for p3 in adjMap[p2]:\n",
    "                    if p3 in adjMap[p1]:\n",
    "                        res += 1\n",
    "                        \n",
    "        return res\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "\n",
    "\n",
    "        #given the undirected graph, we set directions to the graph to reduce search time\n",
    "        #going from undirected graph corridors to directed graph g\n",
    "        # g = defaultdict(set)\n",
    "        # for u, v in corridors:\n",
    "        #     if u < v:\n",
    "        #         g[u].add(v)\n",
    "        #     else:\n",
    "        #         g[v].add(u)\n",
    "\n",
    "        # res = 0\n",
    "        # for p1 in range(1, n + 1):\n",
    "        #     for p2 in g[p1]:\n",
    "        #         for p3 in g[p2]:\n",
    "        #             if p3 in g[p1]:\n",
    "        #                 res += 1\n",
    "        # return res\n",
    "    \n",
    "        graph = defaultdict(set)\n",
    "        for i, j in corridors:\n",
    "            graph[i].add(j)\n",
    "            graph[j].add(i)\n",
    "        \n",
    "        ans = 0\n",
    "        for i, j in corridors:\n",
    "            print(len(graph[i] & graph[j]))\n",
    "            ans += len(graph[i] & graph[j])\n",
    "        return ans // 3\n",
    "\n",
    "            \n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        # we go over all nodes and record cycles by it's sum of node values, and add it to result (a set), as if the total value are\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        ans = 0\n",
    "        g = [set() for _ in range(n + 1)]\n",
    "        for a, b in corridors:\n",
    "            g[a].add(b)\n",
    "            g[b].add(a)\n",
    "        for a, b in corridors:\n",
    "            common = g[a] & g[b]\n",
    "            ans += len(common)\n",
    "        return ans // 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict\n",
    "from typing import List\n",
    "from itertools import combinations\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        #求无向图种长度为3的环的数量\n",
    "        #两两枚举每个节点的邻居节点，看同一个点的两个邻居节点是否相邻，即判断是否为长度为3的环\n",
    "        #每个相同的环会被重复统计三次，结果除以3\n",
    "        edges=defaultdict(set)\n",
    "        for i,j in corridors:\n",
    "            edges[i].add(j)\n",
    "            edges[j].add(i)\n",
    "        ans=0\n",
    "        for i in edges.keys():\n",
    "            for j,k in combinations(edges[i],2):#取出两个数作为组合\n",
    "                if j in edges[k]:\n",
    "                    ans+=1\n",
    "        return ans//3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        dic = defaultdict(set)\n",
    "        for f,t in corridors:\n",
    "            dic[f].add(t)\n",
    "            dic[t].add(f)\n",
    "        ans = 0\n",
    "        for f,t in corridors:\n",
    "            ans += len(dic[f]&dic[t])\n",
    "            #print(dic[f],dic[t],dic[f]&dic[t])\n",
    "        return ans // 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for x, y in corridors:\n",
    "            if x != y:\n",
    "                g[x].add(y)\n",
    "                g[y].add(x)\n",
    "        ## 三元环，求公共节点\n",
    "        return sum(len(g[x] & g[y]) for x, y in corridors) // 3\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for u, v in corridors:\n",
    "            g[u].add(v)\n",
    "            g[v].add(u)\n",
    "        tot = 0\n",
    "        for x in range(1, n + 1):\n",
    "            for y in g[x]:\n",
    "                for z in g[x]:\n",
    "                    if x < y < z and (y in g[z] or z in g[y]):\n",
    "                        tot += 1\n",
    "\n",
    "        return tot \n",
    "        \n",
    "\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from typing import List\n",
    "from collections import defaultdict\n",
    "from itertools import combinations\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        adj = defaultdict(set)\n",
    "        for u, v in corridors:\n",
    "            adj[u].add(v)\n",
    "            adj[v].add(u)\n",
    "\n",
    "        res = 0\n",
    "\n",
    "        # 对邻居两两判断\n",
    "        for p1 in range(1, n + 1):\n",
    "            for p2, p3 in combinations(adj[p1], 2):\n",
    "                if p2 in adj[p3]:\n",
    "                    res += 1\n",
    "\n",
    "        return res // 3\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "      neighbour_dict = defaultdict(set)\n",
    "      for i, j in corridors:\n",
    "          neighbour_dict[i].add(j)\n",
    "          neighbour_dict[j].add(i)\n",
    "      count = 0\n",
    "      for i, j in corridors:\n",
    "          count += len(neighbour_dict[i] & neighbour_dict[j])\n",
    "      return count // 3"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from itertools import combinations\n",
    "from collections import defaultdict\n",
    "\n",
    "class Solution:\n",
    "    def numberOfPaths(self, n: int, corridors: List[List[int]]) -> int:\n",
    "        g = defaultdict(set)\n",
    "        for u,v in corridors:\n",
    "            g[u].add(v)\n",
    "            g[v].add(u)\n",
    "        \n",
    "        total = 0\n",
    "        for p1 in range(1,n+1):\n",
    "            for p2,p3 in combinations(g[p1], 2):\n",
    "                if p2 in g[p3]: total+=1\n",
    "        return total//3"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
